package week_six;

import java.util.Arrays;

public class BestTimeToBuyAndSellStockII_122 {
    public int maxProfit(int[] prices) {
        //贪心
        int ans = 0;
        int n = prices.length;
        int minPrice = -1;
        for (int i = 0; i < n; i++) {
            int x = prices[i];
            if (i == n - 1) {
                if (minPrice > -1) {
                    ans += (x - minPrice);
                }
            }
            int y = prices[i + 1];
            if (x < y) {
                if (minPrice == -1) minPrice = x;//不持股，买入
            } else {
                if (minPrice != -1) {//持股，卖出
                    ans += (x - minPrice);
                    minPrice = -1;
                }
            }
        }
        return ans;
    }

    public int maxProfit1(int[] prices) {
        //DP
        int MIN_V = Integer.MIN_VALUE;
        int n = prices.length;
        // Move prices from [0..n-1] to [1..n]
        int c = n / 2;
        int[] pricesIn = new int[n + 1];
        pricesIn[0] = 0;
        for (int i = 1; i <= n; i++) pricesIn[i] = prices[i - 1];
        // Initialize DP array
        int[][][] f = new int[2][2][c + 1];
        Arrays.fill(f[0][0], MIN_V);
        Arrays.fill(f[0][1], MIN_V);
        f[0 & 1][0][0] = 0;

        // DP
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= 1; j++)
                for (int k = 0; k <= c; k++) {
                    f[i & 1][j][k] = f[(i - 1) & 1][j][k];
                    if (j == 0) f[i & 1][0][k] = Math.max(f[i & 1][0][k], f[(i - 1) & 1][1][k] + pricesIn[i]);
                    if (j == 1 && k > 0)
                        f[i & 1][1][k] = Math.max(f[i & 1][1][k], f[(i - 1) & 1][0][k - 1] - pricesIn[i]);
                }
        // Calculate the target
        int ans = 0;
        for (int k = 0; k <= c; k++) ans = Math.max(ans, f[n & 1][0][k]);
        return ans;
    }

}
